package 单周赛.september;

/**
 * @
 * @date 2024/11/17
 */
public class 第424场单周赛 {

    public static void main(String[] args) {

        第424场单周赛 impl = new 第424场单周赛();
        System.out.println(impl.countValidSelections(new int[]{16, 13, 10, 0, 0, 0, 10, 6, 7, 8, 7}));


        int n = 10;  // 假设数组大小为10
        SegmentTree segTree = new SegmentTree(n);

        // 初始化一些区间的更新操作
        segTree.update(0, 5, 3);  // 更新区间[0, 5]加3
        segTree.update(3, 8, 5);  // 更新区间[3, 8]加5
        segTree.update(8, 8, 5);  // 更新区间[3, 8]加5

        // 查询区间最大值
        System.out.println(segTree.query(0, 9));  // 查询区间[0, 9]的最大值

    }

    public int countValidSelections(int[] nums) {
        int cnt = 0;
        int[] preSum = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                if (preSum[i] == preSum[nums.length] - preSum[i]) {
                    cnt += 2;
                } else if (Math.abs(preSum[i] - (preSum[nums.length] - preSum[i])) == 1) {
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public boolean isZeroArray(int[] nums, int[][] queries) {
        int[] diff = new int[nums.length + 1];
        for (int[] query : queries) {
            diff[query[0]]--;
            diff[query[1] + 1]++;
        }

        int curDiffSum = 0;
        for (int i = 0; i < nums.length; i++) {
            curDiffSum += diff[i];
            if (nums[i] + curDiffSum > 0) {
                return false;
            }
        }
        return true;
    }

    public int minZeroArray(int[] nums, int[][] queries) {

        SegmentTree segTree = new SegmentTree(nums.length);
        for (int i = 0; i < nums.length; i++) {
            segTree.update(i, i, nums[i]);
        }
        if (segTree.query(0, nums.length) <= 0) {
            return 0;
        }

        for (int i = 0; i < queries.length; i++) {
            int[] query = queries[i];
            segTree.update(query[0], query[1], -query[2]);

            if (segTree.query(0, nums.length) <= 0) {
                return i + 1;
            }
        }

        return -1;

    }


    static class SegmentTree {
        private int[] tree;       // 线段树
        private int[] lazy;       // 懒标记数组
        private int n;

        // 构造函数，初始化线段树和懒标记数组
        public SegmentTree(int size) {
            this.n = size;
            this.tree = new int[4 * n];  // 线段树大小
            this.lazy = new int[4 * n];  // 懒标记数组大小
        }

        // 传播懒标记
        private void pushDown(int node, int start, int end) {
            if (lazy[node] != 0) {
                tree[node] += lazy[node];  // 更新当前节点的值

                // 如果不是叶节点，传递懒标记到左右子节点
                if (start != end) {
                    lazy[2 * node] += lazy[node];
                    lazy[2 * node + 1] += lazy[node];
                }

                // 清空当前节点的懒标记
                lazy[node] = 0;
            }
        }

        // 区间更新
        public void update(int l, int r, int value) {
            updateRange(1, 0, n - 1, l, r, value);
        }

        // 区间更新的递归实现
        private void updateRange(int node, int start, int end, int l, int r, int value) {
            pushDown(node, start, end);

            if (start > end || start > r || end < l) return;  // 当前区间不相关

            if (start >= l && end <= r) {  // 当前区间完全在更新范围内
                lazy[node] += value;  // 标记懒更新
                pushDown(node, start, end);  // 更新当前节点的值
                return;
            }

            // 否则继续递归更新左右子树
            int mid = (start + end) / 2;
            updateRange(2 * node, start, mid, l, r, value);
            updateRange(2 * node + 1, mid + 1, end, l, r, value);

            // 更新当前节点
            tree[node] = Math.max(tree[2 * node], tree[2 * node + 1]);
        }

        // 区间查询
        public int query(int l, int r) {
            return queryMax(1, 0, n - 1, l, r);
        }

        // 区间查询的递归实现
        private int queryMax(int node, int start, int end, int l, int r) {
            pushDown(node, start, end);

            if (start > end || start > r || end < l) return Integer.MIN_VALUE;  // 当前区间不相关

            if (start >= l && end <= r) return tree[node];  // 当前区间完全在查询范围内

            int mid = (start + end) / 2;
            int leftMax = queryMax(2 * node, start, mid, l, r);
            int rightMax = queryMax(2 * node + 1, mid + 1, end, l, r);

            return Math.max(leftMax, rightMax);  // 返回左右子树的最大值
        }

    }
}
